package com.peng.old.sort;


import com.peng.old.util.SortUtil;

/**
 * 选择排序
 */
public class SelectionSort {
    public static void main(String[] args) {
//        int[] array = SortUtil.makeRandomArray(10000);
        Integer n1 = new Integer(5);
        Integer n2 = new Integer(5);
        Integer[] array = new Integer[]{n1,3,n2,2,1};
        print(array);
        test1(array);
        print(array);
        System.out.println();
//        System.out.println(SortUtil.checkResult(array));

    }

    /**
     * 简单选择排序
     * @param arr
     */
    static void test1(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minPos = i;
            boolean needSwap = false;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minPos] > arr[j]) {
                    minPos = j;
                    needSwap = true;
                }
            }
            if (needSwap) {
                SortUtil.swap(arr, i, minPos);
            }

        }
    }

    static void test1(Integer[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minPos = i;
            boolean needSwap = false;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minPos] > arr[j]) {
                    minPos = j;
                    needSwap = true;
                }
            }
            if (needSwap) {
                SortUtil.swap(arr, i, minPos);
            }

        }
    }

    /**
     * 选择排序优化：
     * 每次取最大值和最小值
     */
    static void test2(int[] arr) {
        for (int i = 0; i < arr.length/2; i++) {
            int minPos = i;

            boolean needMin = false;
            boolean needMax = false;
            int lastIdx = arr.length-i-1;
            int maxPos = lastIdx;
            //需要在最开始判断如果大于就进行交互，避免两个数又大于又小于的情况
            if(arr[i]>arr[maxPos]){
                SortUtil.swap(arr,lastIdx,i);
            }
            for (int j = i+1; j <arr.length-i ; j++) {
                if(arr[j]>arr[maxPos]){
                    maxPos = j;
                    needMax = true;
                }
                if(arr[j]<arr[minPos]){
                    minPos = j;
                    needMin = true;
                }

            }

            if(needMax){
                SortUtil.swap(arr,lastIdx,maxPos);
            }

            if(needMin){
                SortUtil.swap(arr,i,minPos);
            }



        }
    }




    static void print(Integer[] arr){
        for (Integer integer : arr) {

            System.out.print( integer+":"+  System.identityHashCode(integer)+" ");
        }
        System.out.println();
    }
}
